package J20241015_BinarySearchTree;

import com.sun.source.tree.Tree;

import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description: 二叉搜索树的实现
 * User: 王圆豪
 * Date: 2024-10-15
 * Time: 20:21
 */
public class BinarySearchTree<E extends Comparable<E>>{
    static class TreeNode<E>{
        E val;
        TreeNode<E> left;
        TreeNode<E> right;

        public TreeNode(E val) {
            this.val = val;
        }
    }

    private TreeNode<E> root;

    //删除
    public void remove(E key) {
        TreeNode<E> cur = root;
        TreeNode<E> parent = null;
        while(cur != null) {
            if (cur.val.compareTo(key) > 0) {
                parent = cur;
                cur = cur.left;
            }else if (cur.val.compareTo(key) < 0) {
                parent = cur;
                cur = cur.right;
            }else {
                removeNode(parent, cur);
                return;
            }
        }
    }

    private void removeNode(TreeNode<E> parent, TreeNode<E> cur) {
        if (cur.left == null){
            if (cur == parent){
                root = cur.right;
            }else if (cur == parent.left){
                parent.left = cur.right;
            }else {
                parent.right = cur.right;
            }
        }else if(cur.right == null){
            if (cur == parent){
                root = cur.left;
            }else if (cur == parent.left){
                parent.left = cur.left;
            }else {
                parent.right = cur.left;
            }
        }else {
            TreeNode<E> p = cur;
            cur = cur.left;
            while(cur.right != null){
                parent = cur;
                cur = cur.right;
            }
            p.val = cur.val;
            if (parent.right == cur){
                parent.right = cur.left;
            }else {
                parent.left = cur.left;
            }
        }
    }

    //查找
    public TreeNode<E> search(E key){
        TreeNode<E> cur = root;
        while (cur != null){
            if (cur.val.compareTo(key) > 0){
                cur = cur.left;
            }else if (cur.val.compareTo(key) < 0){
                cur = cur.right;
            }else {
                return cur;
            }
        }
        return null;
    }

    //插入
    public void insert(E key){
        if (root == null) root = new TreeNode<>(key);
        else {
            TreeNode<E> cur = root;
            while (true){
                if (cur.val.compareTo(key) >= 0){
                    if (cur.left == null){
                        cur.left = new TreeNode<>(key);
                        return;
                    }
                    cur = cur.left;
                }else if (cur.val.compareTo(key) < 0){
                    if (cur.right == null){
                        cur.right = new TreeNode<>(key);
                        return;
                    }
                    cur = cur.right;
                }
            }
        }
    }

    //打印————层序遍历
    public void display(){
        Print(root);
    }
    private void Print(TreeNode<E> root){
        if (root == null) return;
        Queue<TreeNode<E>> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()){
            TreeNode<E> tmp = q.poll();
            if (tmp.left != null) q.offer(tmp.left);
            if (tmp.right != null) q.offer(tmp.right);
            System.out.print(tmp.val.toString() + " ");
        }
    }
}
